package main

func canMeasureWater(x int, y int, target int) bool {
	visited := map[string]struct{}{}
	success := false
	var bfs func(c1, c2 int)
	bfs = func(c1, c2 int) {
		if c1 == target || c2 == target || c1+c2 == target {
			success = true
			return
		}
		status := strconv.Itoa(c1) + "-" + strconv.Itoa(c2)
		if _, ok := visited[status]; ok {
			return
		}
		visited[status] = struct{}{}

		// fill x
		if c1 < x {
			bfs(x, c2)
			if success {
				return
			}
		}
		// fill y
		if c2 < y {
			bfs(c1, y)
			if success {
				return
			}
		}
		// empty x
		if c1 > 0 {
			bfs(0, c2)
			if success {
				return
			}
		}
		// empty y
		if c2 > 0 {
			bfs(c1, 0)
			if success {
				return
			}
		}
		// x -> y
		if c1+c2 > y {
			// y overflow
			bfs(c1-(y-c2), y)
			if success {
				return
			}
		} else {
			// c1 + c2 <= y
			bfs(0, c1+c2)
			if success {
				return
			}
		}
		// y -> x
		if c1+c2 > x {
			bfs(x, c2-(x-c1))
			if success {
				return
			}
		} else {
			bfs(c1+c2, 0)
			if success {
				return
			}
		}
	}
	bfs(0, 0)
	return success
}
